/**
 * 35. 搜索插入位置
 * <p>
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 示例 1:
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例 2:
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * <p>
 * https://leetcode.cn/problems/search-insert-position/
 */
public class SearchInsertPosition {
    public static void main(String[] args) {

        int number = 1000;
        long time = 0;
        long memory = 0;
        for (int i = 0; i < number; i++) {
            Runtime r = Runtime.getRuntime();
            r.gc();//计算内存前先垃圾回收一次
            long start = System.currentTimeMillis();//开始Time
            long startMem = r.totalMemory(); // 开始Memory

            int[] nums = {1, 3, 5, 6};
            int target = 5;
            int[] nums1 = {1, 3, 5, 6};
            int target1 = 2;
            int[] nums2 = {1, 3, 5, 6};
            int target2 = 7;
            int[] nums3 = {1, 3, 4, 5, 6};
            int target3 = 7;
            int[] nums4 = {1, 3, 4, 5, 6, 8, 11};
            int target4 = 10;
            int[] nums5 = {1, 4, 5, 6, 8, 11};
            int target5 = 2;
            searchInsert_1(nums, target);
            searchInsert_1(nums1, target1);
            searchInsert_1(nums2, target2);
            searchInsert_1(nums3, target3);
            searchInsert_1(nums4, target4);
            searchInsert_1(nums5, target5);


            long endMem = r.freeMemory(); // 末尾Memory
            long end = System.currentTimeMillis();//末尾Time
            //输出
            time += end - start;
            memory += (startMem - endMem);
        }
        System.out.println("总耗时：" + time + "ms  总内存：" + (memory / 1024) + "KB 平均耗时：" + (time / number) + "ms  平均内存：" + (memory / number / 1024) + "KB");
    }

    /**
     * 23ms  2247785KB  0ms  2247KB(输出结果判断 System.out.println(searchInsert(nums, target) == 2))
     * 0ms  2064356KB  0ms  2064KB
     */
    private static int searchInsert(int[] nums, int target) {
        if (nums[0] >= target) return 0;
        for (int i = 1; i < nums.length; i++) {
            int previous = nums[i - 1];
            int num = nums[i];
            if (num == target || (target > previous && target < num)) return i;
        }
        return nums.length;
    }

    /**
     * 二分法解法（来着评论）
     * <p>
     * 总耗时：0ms  总内存：2054383KB 平均耗时：0ms  平均内存：2054KB
     */
    private static int searchInsert_1(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target)
                l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }


}
